package DP;

import java.util.*;

/**
 * @Author: Gosin
 * @Date: 2020/5/29 13:51
 * 给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。
 * 任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
 * 然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
 * 你需要计算完成所有任务所需要的最短时间。
 *
 */
public class LeastInterval {
    public static void main(String[] args) {
//        char[] tasks = {'A','A','A','B','B','B'};
        char[] tasks = {'A','A','A','A','B','B','B','B','C','C','C','C','D','D','D','D','E','F'};
        LeastInterval interval = new LeastInterval();
        int i = interval.leastInterval_DP(tasks, 4);
        System.out.println(i);
    }

    /**
     * 采用优先队列的方式（主要是想锻炼一下优先队列的使用方式），时间复杂度为，O(M),M为时间
     * @param tasks
     * @param n
     * @return
     */
    public int leastInterval(char[] tasks, int n) {
        //贪心思想：任务出现次数多的情况尽可能先去做
        //计数器
        int[] nums = new int[26];
        for(int i =0;i<tasks.length;i++){
            nums[tasks[i]-'A']++;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(26, Collections.reverseOrder());
        for(int i =0;i<26;i++){
            if(nums[i]>0){
                priorityQueue.offer(nums[i]);
            }
        }
        int time = 0;
        while(!priorityQueue.isEmpty()){
            int i=0;
            List<Integer> temps = new ArrayList<>();//用于存储出队列中大于1的数据，方便进步循环
            while(i<=n){
                if(!priorityQueue.isEmpty()){
                    if(priorityQueue.peek()>1){
                        temps.add(priorityQueue.poll()-1);
                    }else{
                        priorityQueue.poll();
                    }
                }
                i++;//计算时间间隔
                time++;//计算总时间
                if(priorityQueue.isEmpty()&&temps.size()==0){
                    break;
                }
            }
            for(Integer temp:temps){
                priorityQueue.add(temp);
            }
        }
        return time;
    }

    /**
     * 采用动态规划的思想
     * 首先算出出现次数最多的任务A，次数为n
     * 那么其空闲时间是(n-1)*P
     * 其他的任务按照次数由大到小依次执行，
     * 如果任务数==n，那么所消耗的空闲时间为n-1，总时间需要额外加上1个单位
     * 如果任务数<n,所消耗的空闲时间为当前任务数的个数
     * 最后看空闲时间是否还有剩余，如果有的话，那么最短消耗的时间就是，任务总数+剩余空闲时间
     * 如果没有的话，时间间隔不再是限制条件，最短的时间消耗为任务总数。
     * @param tasks
     * @param n
     * @return
     */
    public int leastInterval_DP(char[] tasks, int n) {
        if(tasks.length<0){return 0;}
        int[] nums = new int[26];
        for(char task:tasks){
            nums[task-'A']++;
        }
        Arrays.sort(nums);
        int m = nums[25]-1;
        int freeTime = m*n;
        for(int i=24;i>=0&&nums[i]>0;i--){
            freeTime -= Math.min(m,nums[i]);
        }
        return freeTime>0?tasks.length+freeTime:tasks.length;

    }
}
